package com.arron.algorithm.leetcodetop100.链表;

import com.arron.algorithm.ListNode;

import java.util.List;

public class 反转链表II {


    ListNode temp;

    public ListNode reverseBetween(ListNode head, int left, int right) {

        if (left == 1){


            return reverse(head, right);
        }

        head.next = reverseBetween(head.next, left - 1, right - 1);

        return head;
    }

    //反转前n 个节点
    public ListNode reverse(ListNode head,int n){
        if(n == 1){
            temp = head.next;
            return head;
        }

        ListNode root = reverse(head.next, n - 1);

        ListNode p = head.next;

        p.next = head;
        head.next = temp;


        return root;
    }



    // 直接反转整个链表，返回最后一个根节点
    public ListNode reverse(ListNode head){

        if (head == null || head.next == null){
            return head;
        }

        ListNode lastNode = reverse(head.next);
        ListNode temp = head.next;
        head.next = null;
        temp.next = head;
        return lastNode;

    }


    public static void main(String[] args) {
        反转链表II reverseListNodeII = new 反转链表II();

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        ListNode node = reverseListNodeII.reverseBetween(node1, 2, 4);
        System.out.println(node);

    }




}
